/*3.  Reversing Linked List 根据某大公司笔试题改编的
2014年春季PAT真题，不难，可以尝试；*/

#include <stdio.h>
#include <stdlib.h>
typedef struct Node *list;
struct Node {
    int adress;
    int data;
    int next;
    list link;
};

void attach(int adress, 
            int data, 
            int next, 
            list *prear) {
    list p  = (list)malloc(sizeof(struct Node));
    p->adress  = adress;
    p->data = data;
    p->next = next;
    p->link = NULL;
    (*prear)->link = p;
    (*prear) = p;
}

list read(int *init_adress, int *N, int *K) {
    scanf("%d %d %d", init_adress, N, K);
    int adress, data, next;
    list p, rear, temp;
    p = rear = (list)malloc(sizeof(struct Node));
    for (int i = 0; i < *N; ++i) {
        scanf("%d %d %d", &adress, &data, &next);
        attach(adress, data, next, &rear);
    }
    temp = p;
    p = p->link;
    free(temp);
    return p;
}

list sort_list(int init_adress, int *N, list p) {
    list front, rear, temp;
    int adress, data, next;
    front = rear = (list)malloc(sizeof(struct Node));
    rear->link = NULL;
    list prev = NULL;
    int cnt = 0;
    while (p) {
        list p2 = p;
        prev = NULL;
        while (p2) {
            adress = p2->adress;
            data = p2->data;
            next = p2->next;
            if (adress == init_adress) {
                cnt++;
                attach(adress, data, next, &rear);
                if(prev) prev->link = p2->link;
                else p = p2->link;
                list tt = p2;
                init_adress = p2->next;
                p2 = p2->link;
                free(tt);
            } else {
                prev = p2;
                p2 = p2->link;
            }
        }
        if (init_adress == -1) break;
    }
    temp = front; 
    front = front->link;
    free(temp);
    *N = cnt;
    return front;
}

list reverse(const int N, const int K, list p) {
    list front, rear, temp;
    front = rear = (list)malloc(sizeof(struct Node));
    int tmp_adress[K], tmp_data[K], tmp_next[K];
    int i = 0;
    while (p) {
        tmp_adress[i] = p->adress;
        tmp_data[i] = p->data;
        tmp_next[i] = p->next;
        p = p->link;
        i++;
        if (i == K) {
            for (int j = K-1; j > -1; --j) 
                attach(tmp_adress[j], tmp_data[j], tmp_next[j], &rear);
            i = 0;
        }
    }
    for (int k = 0; k < N % K; ++k) 
        attach(tmp_adress[k], tmp_data[k], tmp_next[k], &rear);
    temp = front;
    front = front->link;
    free(temp);
    list pp = front;
    while(pp) { //update next
        list next_node = pp->link;
        if (next_node) pp->next = next_node->adress;
        else pp->next = -1;
        pp = pp->link;
    }
    return front;
}

void print_res(int N, list p) {
    while (p) {
        if (p->next < 0)
            printf("%05d %d %d\n", p->adress, p->data, p->next);
        else
            printf("%05d %d %05d\n", p->adress, p->data, p->next);
        p = p->link;
    }
}

int main(int argc, char *argv[]) {
    int init_adress, N, K;
    list p = read(&init_adress, &N, &K);
    list sorted_list = sort_list(init_adress, &N, p);
    list res = reverse(N, K, sorted_list);
    print_res(N, res);
    return 0;
}